<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/blog/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />















  
  
  <link href="/blog/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/blog/css/main.css?v=5.1.2" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="数据结构,读书笔记," />








  <link rel="shortcut icon" type="image/x-icon" href="/blog/favicon.ico?v=5.1.2" />






<meta name="description" content="插入排序直接插入排序排序思想将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。 折半插入排序当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2 ,…, Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序 希尔排序在最后一趟增量">
<meta name="keywords" content="数据结构,读书笔记">
<meta property="og:type" content="article">
<meta property="og:title" content="排序">
<meta property="og:url" content="https://git.oschina.net/choichumgming/blog/2017/12/26/排序/index.html">
<meta property="og:site_name" content="choichumgming&#39;s blog">
<meta property="og:description" content="插入排序直接插入排序排序思想将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。 折半插入排序当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2 ,…, Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序 希尔排序在最后一趟增量">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://note.youdao.com/yws/res/1462/WEBRESOURCE584a0baf36fb63c0aaf6d1fcf7a91d7b">
<meta property="og:image" content="http://note.youdao.com/yws/res/1409/WEBRESOURCE097bc89b8764fd056c217e0fbb9c8d35">
<meta property="og:image" content="http://note.youdao.com/yws/res/1412/WEBRESOURCEac9577457e774d9b2462feda0c9bde5e">
<meta property="og:image" content="http://note.youdao.com/yws/res/1415/WEBRESOURCE0c43377de658489aef2b62847a195fca">
<meta property="og:image" content="http://note.youdao.com/yws/res/1418/WEBRESOURCE0e6e033a3854e60b609cedeca547cf59">
<meta property="og:image" content="http://note.youdao.com/yws/res/1468/WEBRESOURCE7e09423b40a34fb42c361ffa4bd00634">
<meta property="og:image" content="http://note.youdao.com/yws/res/1423/WEBRESOURCE78199ec188d4b58f478d3ce3085b21ad">
<meta property="og:image" content="http://note.youdao.com/yws/res/1425/WEBRESOURCEa55ff322a2b5e14fe531177363335059">
<meta property="og:image" content="http://note.youdao.com/yws/res/1434/WEBRESOURCE8113fb2c04e291de2e41c4ebae08c3d8">
<meta property="og:image" content="http://note.youdao.com/yws/res/1437/WEBRESOURCEd6d9fbcc68b7135a62592a1ebd259d62">
<meta property="og:image" content="http://note.youdao.com/yws/res/1440/WEBRESOURCE53038309dfdeeddc5edf74b40fdb9f4a">
<meta property="og:image" content="http://note.youdao.com/yws/res/1456/WEBRESOURCE6a21d647293d2cece68b34dd1663697c">
<meta property="og:image" content="http://note.youdao.com/yws/res/1453/WEBRESOURCE34b4b6cc66dd6c991d03c459d4466198">
<meta property="og:image" content="http://note.youdao.com/yws/res/1459/WEBRESOURCEba0121f2d3d4fea86c8eb1e50182b3f0">
<meta property="og:updated_time" content="2017-12-26T08:36:06.786Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="排序">
<meta name="twitter:description" content="插入排序直接插入排序排序思想将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。 折半插入排序当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2 ,…, Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序 希尔排序在最后一趟增量">
<meta name="twitter:image" content="http://note.youdao.com/yws/res/1462/WEBRESOURCE584a0baf36fb63c0aaf6d1fcf7a91d7b">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Gemini',
    sidebar: {"position":"left","display":"post","offset":12,"offset_float":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: true,
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://git.oschina.net/choichumgming/blog/2017/12/26/排序/"/>





  <title>排序 | choichumgming's blog</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">choichumgming's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">stay foolish,stay hard</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/blog/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/blog/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/blog/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/blog/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-commonweal">
          <a href="/blog/404.html" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-heartbeat"></i> <br />
            
            公益404
          </a>
        </li>
      
        
        <li class="menu-item menu-item-board">
          <a href="/blog/board/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-book"></i> <br />
            
            留言
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://git.oschina.net/choichumgming/blog/blog/2017/12/26/排序/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="choichumgming">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="choichumgming's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">排序</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-12-26T15:23:24+08:00">
                2017-12-26
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/blog/categories/算法与数据结构/" itemprop="url" rel="index">
                    <span itemprop="name">算法与数据结构</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/blog/2017/12/26/排序/#SOHUCS" itemprop="discussionUrl">
                  <span id="changyan_count_unit" class="post-comments-count hc-comment-count" data-xid="2017/12/26/排序/" itemprop="commentsCount"></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        <p><img src="http://note.youdao.com/yws/res/1462/WEBRESOURCE584a0baf36fb63c0aaf6d1fcf7a91d7b" alt="enter image description here"></p>
<h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><h3 id="直接插入排序"><a href="#直接插入排序" class="headerlink" title="直接插入排序"></a>直接插入排序</h3><h4 id="排序思想"><a href="#排序思想" class="headerlink" title="排序思想"></a>排序思想</h4><p>将待排序的记录Ri，插入到已排好序的记录表R1, R2 ,…., Ri-1中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。<br><img src="http://note.youdao.com/yws/res/1409/WEBRESOURCE097bc89b8764fd056c217e0fbb9c8d35" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1412/WEBRESOURCEac9577457e774d9b2462feda0c9bde5e" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1415/WEBRESOURCE0c43377de658489aef2b62847a195fca" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1418/WEBRESOURCE0e6e033a3854e60b609cedeca547cf59" alt="enter image description here"></p>
<h3 id="折半插入排序"><a href="#折半插入排序" class="headerlink" title="折半插入排序"></a>折半插入排序</h3><p>当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2 ,…, Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序</p>
<h3 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h3><p>在最后一趟增量为一的插入排序是，序列基本已经有序–不稳定的排序</p>
<h4 id="排序思想-1"><a href="#排序思想-1" class="headerlink" title="排序思想"></a>排序思想</h4><ol>
<li>先取一个正整数d1(d1&lt;n)作为第一个增量，将全部n个记录分成d1组，把所有相隔d1的记录放在一组中，即对于每个k(k=1, 2,  … d1)，R[k], R[d1+k], R[2d1+k] , …分在同一组中，在各组内进行直接插入排序。这样一次分组和排序过程称为一趟希尔排序；</li>
<li>取新的增量d2&lt;d1，重复①的分组和排序操作；直至所取的增量di=1为止，即所有记录放进一个组中排序为止。</li>
</ol>
<p><img src="http://note.youdao.com/yws/res/1468/WEBRESOURCE7e09423b40a34fb42c361ffa4bd00634" alt="enter image description here"></p>
<h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p>基本思想是：每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。<br>简单选择排序<br>又称为直接选择排序)的基本操作是：通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录，然后和第i个记录进行交换，i=1, 2, … n-1 。</p>
<p><img src="http://note.youdao.com/yws/res/1423/WEBRESOURCE78199ec188d4b58f478d3ce3085b21ad" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1425/WEBRESOURCEa55ff322a2b5e14fe531177363335059" alt="enter image description here"></p>
<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><h3 id="排序思想-2"><a href="#排序思想-2" class="headerlink" title="排序思想"></a>排序思想</h3><p>①  对一组待排序的记录，按堆的定义建立堆；<br>②  将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的；<br>③  堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆（这时候需要向下调整），然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区；<br>④  重复上述步骤，直到全部记录排好序为止。<br> <strong>结论：</strong>排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。<br>–是不稳定的排序</p>
<h3 id="堆排序的关键"><a href="#堆排序的关键" class="headerlink" title="堆排序的关键"></a>堆排序的关键</h3><p>①  如何由一个无序序列建成一个堆？<br>②  如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？<br><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line">关键代码：</div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">FilterDown</span><span class="params">(<span class="keyword">int</span> index)</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> Left =index+index,Right=Left+<span class="number">1</span>;</div><div class="line">        <span class="keyword">if</span>(Left&gt;length)<span class="keyword">return</span>;</div><div class="line">        <span class="keyword">int</span> minindex;</div><div class="line">        <span class="keyword">if</span>(Right&gt;length)minindex=Left;</div><div class="line">        <span class="keyword">else</span> minindex=(A[Left]&lt;A[Right])? Left:Right;</div><div class="line">        <span class="keyword">if</span>(A[index]&gt;A[minindex])</div><div class="line">        &#123;</div><div class="line">            <span class="keyword">int</span> t=A[index]; A[index]=A[minindex];A[minindex]=t;</div><div class="line">            FilterDown(minindex);</div><div class="line">        &#125;</div><div class="line">    &#125;</div></pre></td></tr></table></figure></p>
<h2 id="交换排序"><a href="#交换排序" class="headerlink" title="交换排序"></a>交换排序</h2><p>是一类基于交换的排序，系统地交换反序的记录的偶对，直到不再有这样一来的偶对为止。</p>
<h3 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h3><p>–效率最高</p>
<h4 id="排序思想-3"><a href="#排序思想-3" class="headerlink" title="排序思想"></a>排序思想</h4><p>依次比较相邻的两个记录的关键字，若两个记录是反序的(即前一个记录的关键字大于后前一个记录的关键字)，则进行交换，直到没有反序的记录为止</p>
<h4 id="排序过程"><a href="#排序过程" class="headerlink" title="排序过程"></a>排序过程</h4><ol>
<li>首先将L.R[1]与L.R[2]的关键字进行比较，若为反序(L.R[1]的关键字大于L.R[2]的关键字)，则交换两个记录；然后比较L.R[2]与L.R[3]的关键字，依此类推，直到L.R[n-1]与L.R[n]的关键字比较后为止，称为一趟冒泡排序，L.R[n]为关键字最大的记录。</li>
<li>然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作。<br>一般地，第i趟冒泡排序是对L.R[1 … n-i+1]中的记录进行的，因此，若待排序的记录有n个，则要经过n-1趟冒泡排序才能使所有的记录有序。<br><img src="http://note.youdao.com/yws/res/1434/WEBRESOURCE8113fb2c04e291de2e41c4ebae08c3d8" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1437/WEBRESOURCEd6d9fbcc68b7135a62592a1ebd259d62" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1440/WEBRESOURCE53038309dfdeeddc5edf74b40fdb9f4a" alt="enter image description here"><h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3>最坏情况下，时间复杂度为O（n^2）,最好情况下，一直一半一半，O(nlog2n)）速度最快，是不稳定的排序<h4 id="排序思想-4"><a href="#排序思想-4" class="headerlink" title="排序思想"></a>排序思想</h4>通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。<h4 id="排序过程-1"><a href="#排序过程-1" class="headerlink" title="排序过程"></a>排序过程</h4>设待排序的记录序列是R[s…t] ，在记录序列中任取一个记录(一般取R[s])作为参照(又称为基准或枢轴)，以R[s].key为基准重新排列其余的所有记录，方法是：</li>
</ol>
<ul>
<li>所有关键字比基准小的放R[s]之前；</li>
<li>所有关键字比基准大的放R[s]之后。</li>
<li>以R[s].key最后所在位置i作为分界，将序列R[s…t]分割成两个子序列，称为一趟快速排序。</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div></pre></td><td class="code"><pre><div class="line">代码实现：</div><div class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">QuickSort</span><span class="params">(<span class="keyword">int</span> begin, <span class="keyword">int</span> end)</span> </span>&#123;</div><div class="line">        <span class="comment">// TODO Auto-generated method stub</span></div><div class="line">        <span class="keyword">if</span>(begin&gt;=end)<span class="keyword">return</span>;</div><div class="line">        <span class="keyword">int</span> i=begin+<span class="number">1</span>,j=end;</div><div class="line">        <span class="keyword">while</span>(i&lt;=j)&#123;</div><div class="line">            <span class="keyword">while</span>(i&lt;=j &amp;&amp; keys[i]&lt;=keys[begin])i++;</div><div class="line">            <span class="keyword">while</span>(i&lt;=j &amp;&amp; keys[j]&gt;keys[begin])j--;</div><div class="line">            <span class="keyword">if</span>(i&gt;j)&#123;</div><div class="line">                <span class="keyword">int</span> t=keys[begin];</div><div class="line">                keys[begin]=keys[j];</div><div class="line">                keys[j]=t;</div><div class="line">                </div><div class="line">            &#125;<span class="keyword">else</span> &#123;</div><div class="line">                <span class="keyword">int</span> t=keys[i];</div><div class="line">                keys[i]=keys[j];</div><div class="line">                keys[j]=t;</div><div class="line">                </div><div class="line">            &#125;   </div><div class="line">        &#125;</div><div class="line">        QuickSort(begin, j-<span class="number">1</span>);</div><div class="line">        QuickSort(j+<span class="number">1</span>, end);</div><div class="line">        </div><div class="line">    &#125;</div></pre></td></tr></table></figure>
<h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><h3 id="核心算法："><a href="#核心算法：" class="headerlink" title="核心算法："></a>核心算法：</h3><p>合并两个序列，并使它成为一个有序的序列，放回原来的位置  O(nlog2n)），是稳定的排序，（最大的缺点：要用很多额外空间）<br><strong>归并(Merging)</strong> ：是指将<strong>两个或两个以上的有序序列</strong>合并成<strong>一个有序序列</strong>。若采用线性表(无论是那种存储结构)易于实现，其时间复杂度为O(m+n) 。</p>
<h3 id="排序思想-5"><a href="#排序思想-5" class="headerlink" title="排序思想"></a>排序思想</h3><ol>
<li>初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列；</li>
<li>对所有有序子序列进行两两归并，得到[n/2]个长度为2或1的有序子序列——一趟归并；</li>
<li>重复2 ，直到得到长度为n的有序序列为止。<br>   上述排序过程中，子序列总是两两归并，称为2-路归并排序。其核心是如何将相邻的两个子序列归并成一个子序列。设相邻的两个子序列分别为：<br>{R[k], R[k+1], …, R[m]}和{R[m+1], R[m+2],…, R[h]}，将它们归并为一个有序的子序列：<br>{DR[l], DR[l+1], …, DR[m], DR[m+1], …, DR[h] }<br><img src="http://note.youdao.com/yws/res/1456/WEBRESOURCE6a21d647293d2cece68b34dd1663697c" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1453/WEBRESOURCE34b4b6cc66dd6c991d03c459d4466198" alt="enter image description here"><br><img src="http://note.youdao.com/yws/res/1459/WEBRESOURCEba0121f2d3d4fea86c8eb1e50182b3f0" alt="enter image description here"></li>
</ol>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/数据结构/" rel="tag"># 数据结构</a>
          
            <a href="/blog/tags/读书笔记/" rel="tag"># 读书笔记</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/2017/12/26/AVL平衡二叉搜索树/" rel="next" title="AVL平衡二叉搜索树">
                <i class="fa fa-chevron-left"></i> AVL平衡二叉搜索树
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/blog/2017/12/26/堆/" rel="prev" title="堆">
                堆 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
      <!--PC版-->
<div id="SOHUCS" ></div>


    

  </div>
     <div class="comments" id="comments">
       
     </div>
   





        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/blog/images/avatar.gif"
               alt="choichumgming" />
          <p class="site-author-name" itemprop="name">choichumgming</p>
           
              <p class="site-description motion-element" itemprop="description"></p>
          
        </div>
        <nav class="site-state motion-element">

          
            <div class="site-state-item site-state-posts">
              <a href="/blog/archives/">
                <span class="site-state-item-count">15</span>
                <span class="site-state-item-name">日志</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-categories">
              <a href="/blog/categories/index.html">
                <span class="site-state-item-count">5</span>
                <span class="site-state-item-name">分类</span>
              </a>
            </div>
          

          
            
            
            <div class="site-state-item site-state-tags">
              
                <span class="site-state-item-count">6</span>
                <span class="site-state-item-name">标签</span>
              
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="http://www.weibo.com/u/2558763801" target="_blank" title="微博">
                  
                    <i class="fa fa-fw fa-weibo"></i>
                  
                    
                      微博
                    
                </a>
              </span>
            
          
        </div>

        
        

        
        

        


      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#插入排序"><span class="nav-number">1.</span> <span class="nav-text">插入排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#直接插入排序"><span class="nav-number">1.1.</span> <span class="nav-text">直接插入排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#排序思想"><span class="nav-number">1.1.1.</span> <span class="nav-text">排序思想</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#折半插入排序"><span class="nav-number">1.2.</span> <span class="nav-text">折半插入排序</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#希尔排序"><span class="nav-number">1.3.</span> <span class="nav-text">希尔排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#排序思想-1"><span class="nav-number">1.3.1.</span> <span class="nav-text">排序思想</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#选择排序"><span class="nav-number">2.</span> <span class="nav-text">选择排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#堆排序"><span class="nav-number">3.</span> <span class="nav-text">堆排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#排序思想-2"><span class="nav-number">3.1.</span> <span class="nav-text">排序思想</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#堆排序的关键"><span class="nav-number">3.2.</span> <span class="nav-text">堆排序的关键</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#交换排序"><span class="nav-number">4.</span> <span class="nav-text">交换排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#冒泡排序"><span class="nav-number">4.1.</span> <span class="nav-text">冒泡排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#排序思想-3"><span class="nav-number">4.1.1.</span> <span class="nav-text">排序思想</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#排序过程"><span class="nav-number">4.1.2.</span> <span class="nav-text">排序过程</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速排序"><span class="nav-number">4.2.</span> <span class="nav-text">快速排序</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#排序思想-4"><span class="nav-number">4.2.1.</span> <span class="nav-text">排序思想</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#排序过程-1"><span class="nav-number">4.2.2.</span> <span class="nav-text">排序过程</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#归并排序"><span class="nav-number">5.</span> <span class="nav-text">归并排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#核心算法："><span class="nav-number">5.1.</span> <span class="nav-text">核心算法：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#排序思想-5"><span class="nav-number">5.2.</span> <span class="nav-text">排序思想</span></a></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">choichumgming</span>

  
</div>


  <div class="powered-by">
    由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
  </div>

  <span class="post-meta-divider">|</span>

  <div class="theme-info">
    主题 &mdash;
    <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
      NexT.Gemini
    </a>
  </div>


        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/blog/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/blog/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/blog/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=5.1.2"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=5.1.2"></script>



  
  


  <script type="text/javascript" src="/blog/js/src/affix.js?v=5.1.2"></script>

  <script type="text/javascript" src="/blog/js/src/schemes/pisces.js?v=5.1.2"></script>



  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=5.1.2"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=5.1.2"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=5.1.2"></script>



  


  




	





  





  




  
    <script type="text/javascript">
    (function(){
      var appid = 'cytnT5dky';
      var conf = '56c170b7352bd027682e3707e9eb5071';
      var width = window.innerWidth || document.documentElement.clientWidth;
      if (width < 960) {
      window.document.write('<script id="changyan_mobile_js" charset="utf-8" type="text/javascript" src="https://changyan.sohu.com/upload/mobile/wap-js/changyan_mobile.js?client_id=' + appid + '&conf=' + conf + '"><\/script>'); } else { var loadJs=function(d,a){var c=document.getElementsByTagName("head")[0]||document.head||document.documentElement;var b=document.createElement("script");b.setAttribute("type","text/javascript");b.setAttribute("charset","UTF-8");b.setAttribute("src",d);if(typeof a==="function"){if(window.attachEvent){b.onreadystatechange=function(){var e=b.readyState;if(e==="loaded"||e==="complete"){b.onreadystatechange=null;a()}}}else{b.onload=a}}c.appendChild(b)};loadJs("https://changyan.sohu.com/upload/changyan.js",function(){
        window.changyan.api.config({appid:appid,conf:conf})});
      }
    })();
    </script>
    <script type="text/javascript" src="https://assets.changyan.sohu.com/upload/plugins/plugins.count.js"></script>
  





  





  

  

  

  

  

  

</body>
</html>
